package 合并两个有序数组;

import java.util.Arrays;

/**
 * 合并两个有序数组
 * 两个有序整数数组nums1和nums2，将nums2合并到nums1中，使用nums1成为一个有序数组。
 * <p>
 * 初始化nums1和nums2的元素数量分别为m和n。假设nums1的空间大小等于m+n，这样它就有足够的空间保存来自nums2的元素。
 */
public class Solution {
    public static void main(String[] args) {


        int[] src = new int[]{1, 3, 5, 7, 9, 0, 0, 0, 0};
        int[] nums2 = new int[]{2, 4, 6, 8};

        int[] nums1 = new int[src.length];
        System.arraycopy(src, 0, nums1, 0, src.length);
        int[] merge = merge(nums1, 5, nums2, 4);
        System.out.println("merge = " + Arrays.toString(merge));

        nums1 = new int[src.length];
        System.arraycopy(src, 0, nums1, 0, src.length);
        merge = merge2(nums1, 5, nums2, 4);
        System.out.println("merge = " + Arrays.toString(merge));

        nums1 = new int[src.length];
        System.arraycopy(src, 0, nums1, 0, src.length);
        merge = merge3(nums1, 5, nums2, 4);
        System.out.println("merge = " + Arrays.toString(merge));

        nums1 = new int[src.length];
        System.arraycopy(src, 0, nums1, 0, src.length);
        merge = merge4(nums1, 5, nums2, 4);
        System.out.println("merge = " + Arrays.toString(merge));

    }

    /***
     * 系统函数
     * 时间复杂度O((N+M)*log(N+M))
     */
    public static int[] merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n);
        Arrays.sort(nums1);
        return nums1;
    }

    /***
     * 双指针
     * 时间复杂度O(N+M)
     * 空间复杂度O(N+M)
     */
    public static int[] merge2(int[] nums1, int m, int[] nums2, int n) {

        int[] res = new int[m + n];

        int p1 = 0, p2 = 0;

        for (int i = 0; i < res.length; i++) {

            if (p1 >= m) {
                // nums1 处理完，直接给nums2
                res[i] = nums2[p2];
                p2++;
                continue;
            }
            if (p2 >= n) {
                // nums2 处理完，直接给nums1
                res[i] = nums1[p1];
                p1++;
                continue;
            }

            if (nums1[p1] <= nums2[p2]) {
                res[i] = nums1[p1];
                p1++;
            } else {
                res[i] = nums2[p2];
                p2++;
            }
        }

        return res;
    }

    /***
     * 双指针
     * 时间复杂度O(N+M)
     * 空间复杂度O(N+M)
     */
    public static int[] merge3(int[] nums1, int m, int[] nums2, int n) {

        int[] res = new int[m + n];

        int p = 0, p1 = 0, p2 = 0;

        while (p1 < m && p2 < n) {
            res[p++] = nums1[p1] <= nums2[p2] ? nums1[p1++] : nums2[p2++];
        }

        if (p1 == m) {
            System.arraycopy(nums2, p2, res, p, res.length - p);
        } else {
            System.arraycopy(nums1, p1, res, p, res.length - p);
        }

        return res;
    }

    /***
     * 双指针(从后向前遍历)
     * 时间复杂度O(N+M)
     */
    public static int[] merge4(int[] nums1, int m, int[] nums2, int n) {
        int p = m + n - 1, p1 = m - 1, p2 = n - 1;

        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums1[p1] >= nums2[p2] ? nums1[p1--] : nums2[p2--];
        }

        if (p1 < 0) {
            System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
        }
        return nums1;
    }
}
